package q778_swimInWater;

import UnionTemplate.UF;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    int rows, cols;
    /*
    与1631完全相同解法的一道题
    只是我们将权重的考察变为了两个节点之间较高的高度
    也就是意味着，如果两个点要被union，与t相同的水位也就要达到两者之间较高的高度才行
    最后考察水位什么时候才能使得0号节点和最后一个节点相互union
     */
    public int swimInWater(int[][] grid) {
        List<int[]> edges = new ArrayList<>();
        rows = grid.length;
        cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i > 0) edges.add(new int[]{getIndex(i - 1, j), getIndex(i, j), Math.max(grid[i - 1][j], grid[i][j])});
                if (j > 0) edges.add(new int[]{getIndex(i, j - 1), getIndex(i, j), Math.max(grid[i][j - 1], grid[i][j])});
            }
        }
        edges.sort(Comparator.comparingInt(edge -> edge[2]));
        UF uf = new UF(rows * cols);

        for (int[] edge : edges) {
            int x = edge[0], y = edge[1], weight = edge[2];
            uf.union(x, y);

            if (uf.isConnected(0, rows * cols - 1)) {
                return weight;
            }
        }
        return 0;
    }

    private int getIndex(int i, int j) {
        return i * cols + j;
    }
}

